package com.dy.数学.计数质数;
/*
计数质数
统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 */
public class Solution {
    //超时答案。。。。。
    public static int countPrimes(int n) {
        int count = 0 ;
        for(int i =2;i<n;i++){
            if(isPrime(i)){
                System.out.println(i);
                count++;
            }
        }
        return count;
    }
    public static boolean isPrime(int n){
        for(int i=2;i<n;i++){
            if(n%i ==0){
                return false;
            }
        }
        return true;
    }

    public static int countPrimes2(int n) {
        if (n <= 1) {
            return 0;
        }
        int count=0;
        boolean[] notPrime = new boolean[n];
        for(int i =2;i<n;i++){
            if(!notPrime[i]){
                count++;
                System.out.println(i);
                for(int j=2;i*j<n;j++){
                    notPrime[i*j] = true;
                }
            }
        }
        return count;

    }

    public int countPrimes3(int n) {
        boolean[] noPrime = new boolean[n+1];
        int count=0;
        for(int i = 2;i<Math.sqrt(n);i++){
            if(!noPrime[i]){
                for(int j=i*i;j<n;j+=i){
                    noPrime[j] = true;
                }
            }
        }
        for(int j=2;j<n;j++){
            if(!noPrime[j]){
                count++;
            }
        }
        return count;
    }
}
